/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._414;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3, 2, 1]
 * <p>
 * 输出: 1
 * <p>
 * 解释: 第三大的数是 1.
 * 示例 2:
 * <p>
 * 输入: [1, 2]
 * <p>
 * 输出: 2
 * <p>
 * 解释: 第三大的数不存在, 所以返回最大的数 2 .
 * 示例 3:
 * <p>
 * 输入: [2, 2, 3, 1]
 * <p>
 * 输出: 1
 * <p>
 * 解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
 * 存在两个值为2的数，它们都排第二。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._414
 * @ClassName: ThirdMaximum
 * @Author: linyaonan
 * @Date: 2019/12/27 15:04
 */
public class ThirdMaximum {

    public int thirdMax(int[] nums) {
        Arrays.sort(nums);
        int max = nums[nums.length - 1];
        int second = max;
        int index = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] != second) {
                if (index == 2) {
                    return nums[i];
                } else {
                    second = nums[i];
                    index++;
                }
            }
        }
        return max;
    }

    public int thirdMax2(int[] nums) {
        //先判断数组中的元素是不是空，数据是不是合法的
        if (nums == null || nums.length == 0) {
            throw new RuntimeException("error");
        }
        //定义一个treeSet自动排序，并且去重
        TreeSet<Integer> set = new TreeSet<>();
        //把数组中的元素都放到set里
        for (Integer elem : nums) {
            set.add(elem);
            //如果set的元素个数大于了3，那么我们就把第一个位置的值移除去。因为是排好序的，第一个数为最小的一个。我们保证set里只存放3个元素，第一个元素就是第三个大的数
            if (set.size() > 3) {
                set.remove(set.first());
            }
        }
        //判断set元素个数是大于还是小3，小于的把set最后一个元素返回来也就是最大的。如果不是小于3的。那就返回第一个。也就是第三大的元素
        // set.last() 里面最大的元素
        return set.size() < 3 ? set.last() : set.first();
    }

}
